Corelab Seminar
2010-2011
Evangelos Bampas
Almost optimal asynchronous rendezvous in infinite multidimensional grids
Abstract.
Two anonymous mobile agents (robots) moving in an asynchronous manner have to meet in an infinite grid of dimension
$\delta>0$, starting from two arbitrary positions at distance at most d. Since the problem is clearly infeasible in such general setting, we assume
that the grid is embedded in a $\delta$-dimensional Euclidean space and that each agent knows the Cartesian coordinates of its own initial position
(but not the one of the other agent). We design an algorithm permitting the agents to meet after traversing a trajectory of length $O(d^\delta polylog d)$.
This bound subsumes the main result of [Collins et al, 2010] for the special case of 2-dimensional grids. The algorithm is almost optimal, since the
$\Omega(d^\delta)$ lower bound is straightforward.
(joint work with J. Czyzowicz, L. Gasieniec, D. Ilcinkas, and A. Labourel)